//给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 
//
// 
//
// 说明： 
//
// 
// 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 
// 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 
// 
//
// 
//
// 示例： 
//
// 
//输入：
//nums1 = [1,2,3,0,0,0], m = 3
//nums2 = [2,5,6],       n = 3
//
//输出：[1,2,2,3,5,6] 
//
// 
//
// 提示： 
//
// 
// -10^9 <= nums1[i], nums2[i] <= 10^9 
// nums1.length == m + n 
// nums2.length == n 
// 
// Related Topics 数组 双指针 
// 👍 693 👎 0

package com.everyday.algorithm.changyf.leetcode.editor.cn;
public class MergeSortedArray {
    public static void main(String[] args) {
        Solution solution = new MergeSortedArray().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //首先是三个指针，mP指向nums1的尾部，nP指向nums2的尾部，p指向合并数组的尾部。
    //从后往前比较nums[mP]和nums[nP]，依次放在p所在位置。
    //因为数组都是有序的，当mP指向null(mP=-1)的时候，如果nP不指向null时，余下数组按序合并。
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int mP = m-1;
        int nP = n-1;
        int p = m+n-1;
        while (nP>=0 && mP>=0){
            if (nums2[nP] >= nums1[mP]){
                nums1[p] = nums2[nP];
                nP--;
            }else {
                nums1[p] = nums1[mP];
                mP--;
            }
            p--;
        }
        while (nP>=0){
            nums1[nP] = nums2[nP];
            nP--;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}